package com.rui.study.algorithm.P_等差数列划分Ⅱ_子序列;

import java.util.HashMap;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-29 08:04
 **/
public class Solution1_回溯法_未解决 {

    private int count = 0;

    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        for (int i = 0; i < n-2; i++) {
            for (int j = i+1; j < n-1; j++) {
                long diff = (long)A[j] - (long)A[i];
                find(j, 1, diff, A, n);
            }
        }
        return count;
    }

    private void find(int index, int curCount, long diff, int[] A, int n) {
        for (int i = index+1; i < n; i++) {
            long curDiff = (long)A[i] - (long)A[index];
            if (curDiff == diff) {
                if (curCount > 0) {
                    count += 1;
                }
                find(i, curCount + 1, diff, A, n);
            }
        }
    }


    public static void main(String[] args) {
//        int[] a = {1,3,5,7,9};
        int[] a = {0,2000000000,-294967296};
//        int[] a = {1,2,3,4,5,6};

        long start = System.currentTimeMillis();
        Solution1_回溯法_未解决 solution = new Solution1_回溯法_未解决();
        int result = solution.numberOfArithmeticSlices(a);
        long end = System.currentTimeMillis();
        System.out.println("等差数列划分Ⅱ：" + result + ", 耗时[" + (end - start) + "ms]");
    }
}
